Search results for "Fitness landscape"
showing 10 items of 18 documents
Structural bias in population-based algorithms
2014
Abstract Challenging optimisation problems are abundant in all areas of science and industry. Since the 1950s, scientists have responded to this by developing ever-diversifying families of ‘black box’ optimisation algorithms. The latter are designed to be able to address any optimisation problem, requiring only that the quality of any candidate solution can be calculated via a ‘fitness function’ specific to the problem. For such algorithms to be successful, at least three properties are required: (i) an effective informed sampling strategy, that guides the generation of new candidates on the basis of the fitnesses and locations of previously visited candidates; (ii) mechanisms to ensure eff…
Shaping communities of local optima by perturbation strength
2017
Recent work discovered that fitness landscapes induced by Iterated Local Search (ILS) may consist of multiple clusters, denoted as funnels or communities of local optima. Such studies exist only for perturbation operators (kicks) with low strength. We examine how different strengths of the ILS perturbation operator affect the number and size of clusters. We present an empirical study based on local optima networks from NK fitness landscapes. Our results show that a properly selected perturbation strength can help overcome the effect of ILS getting trapped in clusters of local optima. This has implications for designing effective ILS approaches in practice, where traditionally only small per…
Network structure and optimal technological innovation
2019
The role of networks in the emergence, diffusion and evolution of technological innovations has attracted much theoretical and empirical attention. Yet, much of the work has explored the role of undirected and homogeneous networks. In real cases, many networks are directed. The flow of information, benefits or observations is directed from one node towards another node. Real networks are also heterogeneous, for example, few nodes have a high degree while many others have a low degree. In this article, we report on the results of an evolutionary agent-based model in which a group of agents, in our case firms, collectively search a complex (rugged) technological landscape and observe each oth…
Communities of Local Optima as Funnels in Fitness Landscapes
2016
We conduct an analysis of local optima networks extracted from fitness landscapes of the Kauffman NK model under iterated local search. Applying the Markov Cluster Algorithm for community detection to the local optima networks, we find that the landscapes consist of multiple clusters. This result complements recent findings in the literature that landscapes often decompose into multiple funnels, which increases their difficulty for iterated local search. Our results suggest that the number of clusters as well as the size of the cluster in which the global optimum is located are correlated to the search difficulty of landscapes. We conclude that clusters found by community detection in local…
Species loss leads to community closure
2008
Global extinction of a species is sadly irreversible. At a local scale, however, extinctions may be followed by re-invasion. We here show that this is not necessarily the case and that an ecological community may close its doors for re-invasion of species lost from it. Previous studies of how communities are assembled have shown that there may be rules for that process and that limitations are set to the order by which species are introduced and put together. Instead of focusing on the assembly process we randomly generated simple competitive model communities that were stable and allowed for two to 10 coexisting species. When a randomly selected single species was removed from the communit…
Diffusion modeling of COVID-19 under lockdown
2021
Viral immune evasion by sequence variation is a significant barrier to severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) vaccine design and coronavirus disease-2019 diffusion under lockdown are unpredictable with subsequent waves. Our group has developed a computational model rooted in physics to address this challenge, aiming to predict the fitness landscape of SARS-CoV-2 diffusion using a variant of the bidimensional Ising model (2DIMV) connected seasonally. The 2DIMV works in a closed system composed of limited interaction subjects and conditioned by only temperature changes. Markov chain Monte Carlo method shows that an increase in temperature implicates reduced virus diffusi…
Super-fit and population size reduction in compact Differential Evolution
2011
Although Differential Evolution is an efficient and versatile optimizer, it has a wide margin of improvement. During the latest years much effort of computer scientists studying Differential Evolution has been oriented towards the improvement of the algorithmic paradigm by adding and modifying components. In particular, two modifications lead to important improvements to the original algorithmic performance. The first is the super-fit mechanism, that is the injection at the beginning of the optimization process of a solution previously improved by another algorithm. The second is the progressive reduction of the population size during the evolution of the population. Recently, the algorithm…
Effect of Host Species on Topography of the Fitness Landscape for a Plant RNA Virus
2016
[EN] Adaptive fitness landscapes are a fundamental concept in evolutionary biology that relate the genotype of individuals with their fitness. At the end, the evolutionary fate of evolving populations depends on the topography of the landscape, that is, the number of accessible mutational pathways and of possible fitness peaks (i.e, adaptive solutions). For long time, fitness landscapes were only theoretical constructions due to a lack of precise information on the mapping between genotypes and phenotypes. In recent years, however, efforts have been devoted to characterize the properties of empirical fitness landscapes for individual proteins or for microbes adapting to artificial environme…
Predicting Heuristic Search Performance with PageRank Centrality in Local Optima Networks
2015
Previous studies have used statistical analysis of fitness landscapes such as ruggedness and deceptiveness in order to predict the expected quality of heuristic search methods. Novel approaches for predicting the performance of heuristic search are based on the analysis of local optima networks (LONs). A LON is a compressed stochastic model of a fitness landscape's basin transitions. Recent literature has suggested using various LON network measurements as predictors for local search performance.In this study, we suggest PageRank centrality as a new measure for predicting the performance of heuristic search methods using local search. PageRank centrality is a variant of Eigenvector centrali…
RNA viruses as complex adaptive systems
2004
RNA viruses have high mutation rates and so their populations exist as dynamic and complex mutant distributions. It has been consistently observed that when challenged with a new environment, viral populations adapt following hyperbolic-like kinetics: adaptation is initially very rapid, but then slows down as fitness reaches an asymptotic value. These adaptive dynamics have been explained in terms of populations moving towards the top of peaks on rugged fitness landscapes. Fitness fluctuations of varying magnitude are observed during adaptation. Often the presence of fluctuations in the evolution of physical systems indicates some form of self-organization, or where many components of the s…